package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-04-20 16:26
 */
public class QLint5 {
    public int kthLargestElement(int k, int[] nums) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    private int quickSelect(int[] nums, int start, int end, int k) {
        if(start >= end) {
            return nums[k];
        }
        int i = start, j = end;
        int pivot = nums[i + (j - i) / 2];
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }

            while (i <= j && nums[j] > pivot) {
                j--;
            }

            if(i <= j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;

                i++;
                j--;
            }
        }

        if(k <= j) {
            return quickSelect(nums, start, j, k);
        }

        if(k >= i) {
            return quickSelect(nums, i, end, k);
        }

        return nums[k];
    }
}
